package com.huajin.codetest.algorithm;

/**
 *  递归
 *
 * 阶乘：https://docs.pingcode.com/baike/384105
 * 斐波那契
 * 泰波那契
 *
 */
public class RecursionTest {

    public static void main(String[] args) {
//        System.out.println(factorial1(0));
//        System.out.println(factorial2(0));
//        System.out.println(factorial3(0));
//        System.out.println(factorial1(1));
//        System.out.println(factorial2(1));
//        System.out.println(factorial3(1));
//        System.out.println(factorial1(4));
//        System.out.println(factorial2(4));
//        System.out.println(factorial2(4));

//        System.out.println(tribonacci(3));
//        System.out.println(tribonacci(4));
//        System.out.println(tribonacci(25));

//        System.out.println(fib(0));
//        System.out.println(fib(1));
//        System.out.println(fib(2));
//        System.out.println(fib2(0));
//        System.out.println(fib2(1));
//        System.out.println(fib2(2));

//        System.out.println(climbStairs(1));
//        System.out.println(climbStairs(2));
//        System.out.println(climbStairs(3));


        System.out.println(isPowerOfTwo(0));
        System.out.println(isPowerOfTwo(1));
        System.out.println(isPowerOfTwo(16));
        System.out.println(isPowerOfTwo(3));
        System.out.println(isPowerOfTwo(6));
        System.out.println(isPowerOfTwo(-2));


    }

    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        return n % 2 == 0 && isPowerOfTwo(n / 2);
    }

    public static boolean isPowerOfTwo2(int n) {
        return n > 0 &&  (n & (n - 1)) == 0;
    }

    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    /**
     * 斐波那契
     */
    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0;
        int b = 1;
        int c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static int fib2(int n) {
        if (n <= 1) {
            return n;
        }
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }

    /**
     * 泰波那契
     */
    public static int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int[] tribonacci = new int[n + 1];
        tribonacci[0] = 0;
        tribonacci[1] = 1;
        tribonacci[2] = 1;
        for (int i = 3; i <= n; i++) {
            tribonacci[i] = tribonacci[i - 3] + tribonacci[i - 2] + tribonacci[i - 1];
        }
        return tribonacci[n];
    }

    /**
     * 迭代阶乘
     */
    public static int factorial1(int n) {
        if (n == 0) {
            return 1;
        }
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    /**
     * 递归阶乘
     * 栈溢出
     */
    public static int factorial2(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial2(n - 1);
    }

    /**
     * 回溯阶乘
     */
    public static int factorial3(int n) {
        if (n == 0) {
            return 1;
        }
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = n * factorial[i - 1];
        }
        return factorial[n - 1];
    }

}
